package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

//TODO
/**
 * @author 郭辉
 * @className TODO
 * @description 18. 四数之和
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 * 示例 2：
 *
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * -109 <= nums[i] <= 109
 * -109 <= target <= 109
 * 通过次数441,134提交次数1,189,136
 * @date 2023/4/11 17:05
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet18 {

    /**
     * @description: dfs 去重，超时
     * @author: guohui13
     * @date: 2023/4/12 13:59
     **/
    Set<Map<Integer,Integer>> resIndex = new HashSet<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> resSet = new HashSet<>();
        if (nums == null){
            return res;
        }
        dfs(nums,new ArrayList<>(),target);
        Iterator<Map<Integer, Integer>> setIterator = resIndex.iterator();
        while (setIterator.hasNext()){
            Map<Integer, Integer> mapNext = setIterator.next();
            Iterator<Map.Entry<Integer, Integer>> iterator = mapNext.entrySet().iterator();
            List<Integer> tem = new ArrayList<>();
            while (iterator.hasNext()){
                Map.Entry<Integer, Integer> next = iterator.next();
                tem.add(nums[next.getKey()]);
            }
            resSet.add(tem);
        }
        Iterator<List<Integer>> iterator = resSet.iterator();
        while (iterator.hasNext()){
            List<Integer> next = iterator.next();
            res.add(next);
        }
        return res;
    }

    //路径
    //选择
    //返回条件
    public void dfs(int[] nums, List<Integer> track,int target){
        if (track.size() == 4){
            int sum = 0;
            Map<Integer,Integer> tem = new HashMap<>();
            for (int i = 0; i < 4; i++) {
                sum += nums[track.get(i)];
                tem.put(track.get(i),track.get(i));
            }
            if (sum == target){
                resIndex.add(tem);
                return;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            //剪枝
            if (track.contains(i)){
                continue;
            }
            //选择
            track.add(i);
            dfs(nums,track,target);
            //撤销
            track.remove(track.size()-1);

        }
    }
    public List<List<Integer>> fourSumSec(int[] nums, int target) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {

            int l = 0, r = nums.length-1;
            for (int j = 0; j < nums.length; j++) {
                    if (i == j) {
                        continue;
                    }
                    while (l == i || l == j) {
                        l++;
                    }
                    while (r == i || r == j) {
                        r--;
                    }
                while (l < r) {
                    int sum = nums[l] + nums[r] + nums[i] + nums[j];
                    if (sum == target) {
                        Map<Integer, Integer> temp = new HashMap<>();
                        if (temp.get(nums[l]) == null) {
                            temp.put(nums[l], 1);
                        } else {
                            temp.put(nums[l], temp.get(nums[l] + 1));
                        }
                        if (temp.get(nums[r]) == null) {
                            temp.put(nums[r], 1);
                        } else {
                            temp.put(nums[r], temp.get(nums[r] + 1));
                        }
                        if (temp.get(nums[i]) == null) {
                            temp.put(nums[i], 1);
                        } else {
                            temp.put(nums[i], temp.get(nums[i] + 1));
                        }
                        if (temp.get(nums[j]) == null) {
                            temp.put(nums[j], 1);
                        } else {
                            temp.put(nums[j], temp.get(nums[j] + 1));
                        }
                        resIndex.add(temp);
                    }
                    if (sum < target) {
                        l++;
                    }
                    if (sum > target) {
                        r--;
                    }
                }
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        Iterator<Map<Integer, Integer>> iterator = resIndex.iterator();
        while (iterator.hasNext()){
            Map<Integer, Integer> next = iterator.next();
            Iterator<Map.Entry<Integer, Integer>> iterator1 = next.entrySet().iterator();
            List<Integer> list = new ArrayList<>();
            while (iterator1.hasNext()){
                Map.Entry<Integer, Integer> next1 = iterator1.next();
                for (int i = 0; i < next1.getValue(); i++) {
                    list.add(next1.getKey());
                }
            }
            res.add(list);
        }
        return res;
    }

    public static void main(String[] args) {
        Leet18 leet18 = new Leet18();
        int[] param = {1,0,-1,0,-2,2};
        System.out.println(leet18.fourSumSec(param, 0));
    }
}
